package class35;

/**
 * @author zhangchaoliang
 * create 20221.
 * 流程统计每个字符的个数
 *         // 2.遍历字符串，每遍历一个字符就在统计的词频表中把该字符的数量减一
 *         // 当其中某一个字符的数量被减为0时停止遍历，从其实位置开始到结束位置之间选一个
 *         // 最前的字典序最小的字符作为保留字符，在他之前的字符全部删掉，之后的和他相同的字符
 *         // 也删掉。
 *         // 从新进行12步骤直到每个字符都剩一个就找到了字典序最小且无重复字符的字符串
 */
public class RemoveDuplicateLettersLessLexi {

    public static String remove(String str) {
        if (str == null || str.length() < 2) {
            return str;
        }
        int[] map = new int[256];
        for (int i = 0; i < str.length(); i++) {
            map[str.charAt(i)]++;
        }
        int minACSIndex = 0;
        for (int i = 0; i < str.length(); i++) {
            if (--map[str.charAt(i)] == 0) {
                break;
            } else {
                minACSIndex = str.charAt(minACSIndex) > str.charAt(i) ? i : minACSIndex;
            }
        }
        return String.valueOf(str.charAt(minACSIndex)) +
                remove(str.substring(minACSIndex + 1).
                        replaceAll(String.valueOf(str.charAt(minACSIndex)), ""));
    }

    public static void main(String[] args) {
        String str = "dbcacbca";
        System.out.println(remove(str));
    }
}
